# Definition for single linked list.

class Node(object):
    def __init__(self, value, p=None):
        self.data = value;
        self.next = p;

class LinkedList(object):
    def __init__(self):
        self.head = None;

    def __getitem__(self, key):
        if self.isEmpty():
            print('linklist is empty.');
            return;
        elif key < 0  or key > self.getLength():
            print('the given key is error');
            return;
        else:
            return self.getItem(key);

    def __setitem__(self, key, value):
        if self.isEmpty():
            print('linklist is empty.');
            return;

        elif key < 0  or key > self.getLength():
            print('the given key is error');
            return;

        else:
            self.delete(key);
            return self.insert(key);

    def init(self, data):
        if len(data) == 0:
            return;
        self.head = Node(data[0]);
        p = self.head;

        for i in data[1:]:
            node = Node(i);
            p.next = node;
            p = p.next;

    def getLength(self):
        p = self.head;
        length = 0;
        while p is not None:
            length += 1;
            p = p.next;

        return length;

    def isEmpty(self):
        if self.getLength() == 0:
            return True;
        else:
            return False;

    def clear(self):
        self.head = None;

    def append(self, item):
        q = Node(item);
        if self.head is None:
            self.head = q;
        else:
            p = self.head;
            while p.next is not None:
                p = p.next;
            p.next = q;


    def getItem(self, index):
        if self.isEmpty():
            print('Linklist is empty.');
            return;
        j = 0;
        p = self.head;

        while p.next is not None and j < index:
            p = p.next;
            j += 1;

        if j == index:
            return p.data;

        else:
            print('target is not exist!');

    def insert(self, index, item):
        if self.isEmpty() or index < 0 or index > self.getLength():
            print('Linklist is empty.');
            return;

        if index == 0:
            q = Node(item, self.head);
            self.head = q;
            return;

        p = self.head;
        post = self.head;
        j = 0;
        while p.next is not None and j < index:
            post = p;
            p = p.next;
            j += 1;

        if index == j:
            q = Node(item, p);
            post.next = q;

    def delete(self, index):
        if self.isEmpty() or index < 0 or index > self.getLength():
            print('Linklist is empty.');
            return;

        if index == 0:
            self.head = self.head.next;
            return;

        p = self.head;
        post = self.head;
        j = 0;
        while p.next is not None and j < index:
            post = p;
            p = p.next;
            j += 1;

        if index == j:
            post.next = p.next;

    def index(self, value):
        if self.isEmpty():
            print('Linklist is empty.');
            return;

        p = self.head;
        i = 0;
        while p.next is not None and not p.data == value:
            p = p.next;
            i += 1;
        if p.data == value:
            return i;
        else:
            return -1;

    def toString(self):
        if self.isEmpty():
            return '<EMPTY>';
        p = self.head;
        ls = [];
        while p is not None:
            if len(ls) > 0:
                ls.append('->');
            ls.append(str(p.data));
            p = p.next;
        return ''.join(ls);
